package com.linkai.linklist;

import java.util.ArrayList;

/**
 * @Description: 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
 * @Author: 林凯
 * @Date: 2021/10/8 8:29
 */
public class JZ3 {
    public static void main(String[] args) {
        // 思路：采用链表的头插法可以逆转链表
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);

        listNode1.insertNode(listNode2);
        listNode1.insertNode(listNode3);

        ArrayList<Integer> arrayList = printListFromTailToHead(listNode1);
        System.out.println(arrayList);      // [3, 2, 1]
    }

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        /*
            思路：使用链表的头插法倒转链表，形成一个新链表，然后在对该链表进行遍历输出
            构造一个新的链表（这个链表是带头结点的）
            原链表是不带头结点的
        * */
        ListNode head = new ListNode(0);
        ListNode tmp = listNode;
        ArrayList list = new ArrayList();

        while (tmp != null) {
            // 创建一个新结点并将赋值（用已经存在的链表赋值）
            ListNode newList = new ListNode(tmp.val);
            // 将新结点以“头插法”都方式插入到新链表中
            newList.next = head.next;
            head.next = newList;
            tmp = tmp.next;
        }

        tmp = head.next;
        while (tmp != null) {
            list.add(tmp.val);
            tmp = tmp.next;
        }

        return list;

    }
}

